#include <iostream>
#include <queue>
#include <vector>
using namespace std;

vector<bool> vi;
vector<bool> col;
bool isbip = 1;
void dfs(int x, int color, vector<vector<int>>& graph) {
    if (isbip == 0) return;
    if (vi[x]) return;
    vi[x] = 1;
    col[x] = color;
    for (int nei : graph[x]) {
        if (vi[nei]) {
            if (col[nei] == col[x]) {
                isbip = 0;
                return;
            } else {
                continue;
            }
        } else {
            dfs(nei, !color, graph);
        }
    }
}

bool isBipartite(vector<vector<int>>& graph) {
    int n = graph.size();
    vi.resize(n, 0);
    col.resize(n, -1);
    for (int i = 0; i < n; i++) {
        if (!vi[i]) dfs(i, 1, graph);
    }
    return isbip;
}